package com.heima.leetcode.practice;

import java.util.concurrent.ThreadLocalRandom;

/**
 * leetcode 912. 排序数组
 *
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/7 19:27
 */
public class E912 {

    private static final int INSERTION_SORT_THRESHOLD = 32; // 插入排序的阈值

    /**
     * <h3>方法一：冒泡排序，超出时间限制</h3>
     *
     * @param nums 待排序数组
     * @return 排序后的数组
     */
    public int[] sortArray1(int[] nums) {
        int bound = nums.length - 1; // 未排序部分的边界，包含
        // 当前边界大于0时，说明还有元素未排序，继续循环，只有一个的情况也可能冒泡到后面去
        while (bound > 0) {
            int newBound = 0; // 记录新的边界，用于减少循环次数（检查次数），注意不是减少交换次数
            for (int i = 0; i < bound; i++) {
                if (nums[i] > nums[i + 1]) { // 冒泡
                    swap(nums, i, i + 1);
                    newBound = i;
                }
            }
            bound = newBound; // 更新边界
        }
        return nums;
    }

    /**
     * <h3>方法二：选择排序，超出时间限制</h3>
     *
     * @param nums 待排序数组
     * @return 排序后的数组
     */
    public int[] sortArray2(int[] nums) { // 相比于冒泡排序，减少了交换次数，但是不能减少循环次数
        int bound = nums.length - 1; // 未排序部分的边界，包含
        while (bound > 0) { // 边界大于0时，也就是有两个以上元素未排序
            // 1. 查找未排序区间的最大值索引
            int maxIndex = 0;
            for (int i = 1; i <= bound; i++) {
                if (nums[i] > nums[maxIndex]) {
                    maxIndex = i;
                }
            }
            // 2. 交换最大值和边界元素
            if (maxIndex != bound) {
                swap(nums, maxIndex, bound);
            }
            // 3. 边界减一，继续下一轮循环
            bound--; // 很明显，可以改写为for循环
        }
        return nums;
    }

    /**
     * <h3>方法三：堆排序，执行耗时37ms</h3>
     *
     * @param nums 待排序数组
     * @return 排序后的数组
     */
    public int[] sortArray3(int[] nums) {
        MaxHeap heap = new MaxHeap(nums);
        for (int i = 0; i < nums.length - 1; i++) {
            heap.poll();
        }
        return nums;
    }

    /**
     * 大顶堆
     */
    static class MaxHeap {
        int[] arr; // 堆数组
        int size; // 堆大小
        static final int DEFAULT_CAPACITY = 11; // 默认容量

        /**
         * 无参构造
         */
        public MaxHeap() {
            this.arr = new int[DEFAULT_CAPACITY];
            this.size = 0;
        }

        /**
         * 有参构造
         *
         * @param arr 数组
         */
        public MaxHeap(int[] arr) {
            this.arr = arr;
            this.size = arr.length;
            heapify();
        }

        /**
         * heapify()
         */
        private void heapify() {
            // (size - 1 - 1) >> 1 = size >> 1
            for (int i = (size >> 1) - 1; i >= 0; i--) {
                down(i);
            }
        }

        /**
         * 下潜
         *
         * @param parent 下潜节点的索引
         */
        private void down(int parent) {
            int left = (parent << 1) + 1;
            int right = left + 1;
            int max = maxIndex(parent, left, right);
            if (max != parent) {
                swap(parent, max);
                down(max);
            }
        }

        /**
         * 获取父、左子、右子、节点中的最大值
         *
         * @param parent 父节点的索引
         * @param left   左子节点的索引
         * @param right  右子节点的索引
         * @return 最大值索引
         */
        private int maxIndex(int parent, int left, int right) {
            if (left >= size) {
                return parent;
            } else if (right == size) {
                return arr[parent] >= arr[left] ? parent : left;
            } else {
                if (arr[parent] >= arr[left]) {
                    return arr[parent] >= arr[right] ? parent : right;
                } else {
                    return arr[left] >= arr[right] ? left : right;
                }
            }
        }

        /**
         * 交换数组中两个索引处的元素
         *
         * @param index1 索引1
         * @param index2 索引2
         */
        private void swap(int index1, int index2) {
            int temp = arr[index1];
            arr[index1] = arr[index2];
            arr[index2] = temp;
        }

        /**
         * 弹出堆顶元素，并重新堆化
         *
         * @return 堆顶元素
         */
        public int poll() {
            int poll = arr[0];
            swap(0, --size);
            down(0);
            return poll;
        }

        /**
         * 插入元素，并维持堆的性质
         * @param val 待插入元素
         */
        public void put(int val) {
            arr[size++] = val;
            up(size - 1);
        }

        /**
         * 上潜
         * @param child 子节点的索引
         */
        private void up(int child) {
            // 递归边界，如果child是0，说明已经上到了根节点，不需要继续递归了
            if (child == 0){
                return;
            }
            // 递的时候能上潜就上潜，不能就结束递归
            int parent = (child - 1) >> 1;
            if (arr[child] > arr[parent]){
                swap(child, parent);
                // 继续递归
                up(parent);
            }
        }
    }

    /**
     * <h3>方法四：插入排序，超出时间限制</h3>
     *
     * @param nums 待排序数组
     * @return 排序后的数组
     */
    public int[] sortArray4(int[] nums) {
        int bound = 1; // 已排序的部分的右边界（不包含）
        while (bound < nums.length) {
            int inserted = nums[bound]; // 待插入元素
            int index = bound; // 插入位置的索引
            while (index > 0 && nums[index - 1] > inserted) { // index初始是bound，移动的是范围内的元素，最终处理完后会有index--
                nums[index] = nums[index - 1];
                index--; // 不要合并
            }
            if (index != bound) { // 避免插入位置和待插入元素相同时无意义交换
                nums[index] = inserted;
            }
            bound++; // 很明显上述可以改造为for循环
        }
        return nums;
    }

    /**
     * <h3>方法五：希尔排序，执行耗时32ms</h3>
     *
     * @param nums 待排序数组
     * @return 排序后的数组
     */
    public int[] sortArray5(int[] nums) { // 优化版的插入排序，让寻找插入位置时一次移动的更多
        for (int gap = nums.length >> 1; gap >= 1; gap >>= 1) { // 这里的gap指的是分组中一个分组的最多元素个数，99%的组元素个数都是相同的，一般只有一个不相同
            // 对每个组的每位并行排序
            for (int i = gap; i < nums.length; i++) {
                int inserted = nums[i]; // 待插入元素
                int index = i; // 记录插入位置
                while (index > gap - 1 && nums[index - gap] > inserted) { // 插入排序的思想,index最后有一次-gap，index值不能小于gap，否则最后的index会变成负数
                    nums[index] = nums[index - gap];
                    index -= gap;
                }
                if (index != i) { // 避免插入位置和待插入元素相同时无意义交换
                    nums[index] = inserted;
                }
            }
        }
        return nums;
    }

    /**
     * <h3>方法六：自下而上的归并排序，耗时23ms</h3>
     * 这种方法是迭代的，从下层多的小分片到上层多的大分片
     *
     * @param nums 待排序数组
     * @return 排序后的数组
     */
    public int[] sortArray6(int[] nums) {
        int[] result = new int[nums.length];
        // 分组的宽度，占多少元素，初始值为1，因为1个为有序
        for (int width = 1; width < nums.length; width <<= 1) {
            for (int i = 0; i < nums.length; i += (width << 1)) { // 每相邻两个数组的首索引
                // int begin1 = i; // 待合并两个子数组前一个数组起始索引（包含）
                int end1 = Math.min(i + width - 1, nums.length - 1); // 待合并两个子数组前一个数组结束索引（包含）
                // int begin2 = end1 + 1; // 待合并两个子数组后一个数组起始索引（包含）
                int end2 = Math.min(i + (width << 1) - 1, nums.length - 1); // 待合并两个子数组后一个数组结束索引（包含）
                // 两个数组都存在才合并
                merge(nums, i, end1, end2, result); // 这里不能加if判断，实际只有一个数组的时候也需要保存到result数组
            }
            System.arraycopy(result, 0, nums, 0, nums.length); // 处理下一次宽度时，还是用的nums数组，要更新
        }
        return nums;
    }

    /**
     * <h3>方法七：自上而下的归并排序，22ms</h3>
     * 这种方法是递归的，上层多的大分片到从下层多的小分片
     *
     * @param nums 待排序数组
     * @return 排序后的数组
     */
    public int[] sortArray7(int[] nums) {
        int[] result = new int[nums.length];
        sortArray7(nums, 0, nums.length - 1, result);
        return nums;
    }

    /**
     * 自上而下的归并排序递归实现
     * @param nums 待排序数组
     * @param begin 起始索引（包含）
     * @param end 结束索引（包含）
     * @param result 合并结果
     */
    private void sortArray7(int[] nums, int begin, int end, int[] result) {
        // 递归结束条件：当前数组只有一个元素，也就是默认有序
        if (begin == end){
            return;
        }
        // 递归的时候将数组一分为二，分别调用递归排序，然后合并
        int median = (begin + end) >>> 1;
        sortArray7(nums, begin, median, result);
        sortArray7(nums, median + 1, end, result);
        merge(nums, begin, median, end, result);
        // 归的时候将合并的结果覆盖指定范围内的原数组
        System.arraycopy(result, begin, nums, begin, end - begin + 1);
    }

    /**
     * <h3>方法八：归并排序结合插入排序，执行耗时15ms</h3>
     * 这种方法是递归的，上层多的大分片到从下层多的小分片
     *
     * @param nums 待排序数组
     * @return 排序后的数组
     */
    public int[] sortArray8(int[] nums) {
        int[] result = new int[nums.length];
        sortArray8(nums, 0, nums.length - 1, result);
        return nums;
    }

    /**
     * 归并排序结合插入排序递归实现
     * @param nums 待排序数组
     * @param begin 起始索引（包含）
     * @param end 结束索引（包含）
     * @param result 合并结果
     */
    private void sortArray8(int[] nums, int begin, int end, int[] result) {
        // 递归结束条件：当数组元素范围小于32个元素，那么进行插入排序处理小规模数据
        if (end - begin + 1 <= INSERTION_SORT_THRESHOLD){
            insertionSort(nums, begin, end); // 这里就已经把这个范围内排序好了，不会用到中间数组result
            return;
        }
        // 递的时候将数组一分为二，分别调用递归排序
        int median = (begin + end) >>> 1;
        sortArray8(nums, begin, median, result);
        sortArray8(nums, median + 1, end, result);
        // 归的时候将合并的数组，并将合并结果覆盖原始nums数组
        merge(nums, begin, median, end, result);
        System.arraycopy(result, begin, nums, begin, end - begin + 1);
    }

    /**
     * 双指针法合并两个有序数组
     *
     * @param nums   待合并数组
     * @param begin1 待合并数组前一个数组起始索引（包含）
     * @param end1   待合并数组前一个数组结束索引（包含）
     * @param end2   待合并数组后一个数组结束索引（包含）
     * @param result 合并结果
     */
    private void merge(int[] nums, int begin1, int end1, int end2, int[] result) {
        int index1 = begin1;
        int index2 = end1 + 1;
        int index = begin1;
        while (index1 <= end1 && index2 <= end2) {
            if (nums[index1] < nums[index2]) {
                result[index++] = nums[index1++];
            } else {
                result[index++] = nums[index2++];
            }
        }
        if (index1 <= end1) {
            System.arraycopy(nums, index1, result, index, end1 - index1 + 1);
        }
        if (index2 <= end2) {
            System.arraycopy(nums, index2, result, index, end2 - index2 + 1);
        }
    }

    /**
     * <h3>方法9：快速排序，采用罗穆托分区，单边循环快排，执行耗时1646ms</h3>
     *
     * @param nums 待排序数组
     * @return 排序后的数组
     */
    public int[] sortArray9(int[] nums) {
        quickSortLomuto(nums, 0, nums.length - 1);
        return nums;
    }

    /**
     * 罗穆托分区方案快速排序递归实现，单边循环快排组合插入排序
     * @param nums 待排序数组
     * @param begin 起始索引（包含）
     * @param end 结束索引（包含）
     */
    private void quickSortLomuto(int[] nums, int begin, int end) {
        // 递归结束条件：当前范围内只有一个元素，也就是默认有序
        if (begin >= end){ // 大于等于是因为想想只有两个元素分区的时候
            return;
        }
        // 递的时候分区，然后对基准点左边、右边进行快速排序
        int pivot = partitionLomuto(nums, begin, end);
        quickSortLomuto(nums, begin, pivot - 1);
        quickSortLomuto(nums, pivot + 1, end);
    }

    /**
     * 罗穆托分区方案快速排序的分区操作，单边循环快排
     * @param nums 待排序数组
     * @param begin 起始索引（包含）
     * @param end 结束索引（包含）
     * @return 分区好后基准点的索引
     */
    private int partitionLomuto(int[] nums, int begin, int end) {
        // 取随机数作为基准点元素，然后与尾元素交换，让最后一个作为基准点
        int randomIndex = ThreadLocalRandom.current().nextInt(end - begin + 1) + begin;
        swap(nums, randomIndex, end);
        int pivot = nums[end];
        int ge = begin; // ge指针记录大于等于基准点的元素的位置，找到后还应该停下来
        // lt指针对基准点以前的元素遍历，找到小于基准点的元素的索引，如果找到了，并且ge也找到了，则交换
        for (int lt = begin; lt < end; lt++){
            if (nums[lt] < pivot){ // 找到小于基准点的元素
                if (nums[ge] >= pivot && ge != lt){ // ge也找到大于等于基准点的元素，并且lt！=ge是为了减少不必要的交换
                    swap(nums, lt, ge);
                }
                ge++; // ge无论找没找到都要自增一
            }
        }
        swap(nums, ge, end); // 最后ge记录的位置是大于基准点元素的第一个
        return ge;
    }

    /**
     * <h3>方法10：快速排序，采用霍尔分区方案，双边循环快排，执行耗时1644ms</h3>
     *
     * @param nums 待排序数组
     */
    public int[] sortArray10(int[] nums) {
        quickSortHoare(nums, 0, nums.length - 1);
        return nums;
    }

    /**
     * 霍尔分区方案快速排序递归实现，双边循环快排组合插入排序
     * @param nums   待排序数组
     * @param begin 待排序范围的起始索引（包含）
     * @param end   待排序范围的结束索引（包含）
     */
    private void quickSortHoare(int[] nums, int begin, int end) {
        // 递归结束条件：当前范围数组内只有一个元素，这里用大于等于，想象两个元素分区后的情况
        if (begin >= end) {
            return;
        }
        // 递的时候将基准点元素放到合适位置并且把比基准点小的元素放基准点元素左边，比基准点大或等的元素放基准点元素右边
        int pivot = partitionHoare(nums, begin, end);
        // 再对基准点左边的区域和右边的区域进行快速排序
        quickSortHoare(nums, begin, pivot - 1);
        quickSortHoare(nums, pivot + 1, end);
    }

    /**
     * 霍尔分区方案快速排序的分区操作，单边循环快排
     *
     * @param nums   待分区数组
     * @param begin 待分区范围的起始索引（包含）
     * @param end   待分区范围的结束索引（包含）
     * @return 分区好后的基准点元素索引
     */
    private int partitionHoare(int[] nums, int begin, int end) {
        int le = end; // le指针负责找到小于等于基准点的元素
        int gt = begin; // gt指针负责找到大于基准点的元素
        // 随机选择一个元素作为基准点，这样优化的原因是因为当待排序数组是完全倒序的情况下，le指针每走一步都会停下来，gt每次循环都要走到末尾，变成了最坏情况
        int index = ThreadLocalRandom.current().nextInt(end - begin + 1) + begin; // 用随机元素作为基准点，ThreadLocalRandom线程安全
        swap(nums, index, begin); // 将随机元素放到数组最左端
        int pivot = nums[begin]; // 基准点元素
        while (le > gt){ // 当le和gt没有相遇，继续循环
            while (le > gt && nums[le] > pivot){ // le当前位置的元素大于基准点元素，则继续向左移动le指针寻找小于等于基准点的元素，但是le不能减得小于gt
                le--;
            }
            while (le > gt && nums[gt] <= pivot){ // gt当前位置的元素小于等于基准点元素，则继续向右移动gt指针寻找大于基准点的元素，但是gt不能大于le
                gt++;
            }
            // 上述两个while循环不能交换顺序，
            swap(nums, le, gt); // 将le和gt位置的元素交换
        }
        swap(nums, le, begin); // 将基准点元素放到合适位置
        return le; // 返回基准点元素索引
    }

    /**
     * <h3>方法11：快速排序，采用霍尔分区，双边循环快排，结合插入排序，考虑优化重复元素情况，执行耗时18ms</h3>
     *
     * @param nums 待排序数组
     */
    public int[] sortArray11(int[] nums) {
        quickSortFinal(nums, 0, nums.length - 1);
        return nums;
    }

    /**
     * 快速排序递归实现
     *
     * @param nums   待排序数组
     * @param begin 待排序范围的起始索引（包含）
     * @param end   待排序范围的结束索引（包含）
     */
    private void quickSortFinal(int[] nums, int begin, int end) {
        // 递归结束条件：当前范围内数组的个数小到一定程度用插入排序
        if (end - begin + 1 <= INSERTION_SORT_THRESHOLD){
            insertionSort(nums, begin, end);
            return;
        }
        // 递归结束条件：当前范围数组内只有一个元素，这里用大于等于，想象两个元素分区后的情况
        if(begin >= end){
            return;
        }
        // 递的时候将基准点元素放到合适位置并且把比基准点小的元素放基准点元素左边，比基准点大或等的元素放基准点元素右边
        int pivot = partitionFinal(nums, begin, end);
        // 再对基准点左边的区域和右边的区域进行快速排序
        quickSortFinal(nums, begin, pivot - 1);
        quickSortFinal(nums, pivot + 1, end);
    }

    /**
     * 能够处理重复元素的霍尔分区方案
     *
     * @param arr   待分区数组
     * @param begin 待分区范围的起始索引（包含）
     * @param end   待分区范围的结束索引（包含）
     * @return 分区好后的基准点元素索引
     */
    private int partitionFinal(int[] arr, int begin, int end) {
        int le = end; // le指针负责找到小于等于基准点的元素
        int ge = begin + 1; // ge指针负责找到大于等于基准点的元素，初值设置为begin+1是因为找大于等于begin处元素的不包括它本身
        int index = ThreadLocalRandom.current().nextInt(end - begin + 1) + begin; // 随机数优化，线程安全，优化的情况是已经排好序的，不管是降序还是升序，都会有个指针每次都会走完剩下所有元素，时间复杂度回到O(N^2)
        swap(arr, index, begin); // 将随机数处的元素放到数组最左端，用随机数优化也相当于一种妥协，不用随机数的话，遇到最遭情况就会需要分n次区，而不是log n
        int pivot = arr[begin]; // 基准点元素
        while (ge <= le) { // 这里的等号不能少，最后一轮也需要处理
            // ge指针负责找到大于等于基准点的元素
            while (ge <= le && arr[ge] < pivot) { // 就是在前面找到比基准点大的交换到后面去，ge自加但是不饿能超过le
                ge++;
            }
            // le指针负责找到小于等于基准点的元素
            while (ge <= le && arr[le] > pivot) { // 就是在后面找到比基准点小的交换到前面去，le自减但是不饿能小于ge
                le--;
            }
            // 当ge还是小于等于le的时候，交换两个元素
            if (ge <= le) { // 如果上一轮外层while循环退出时，ge和le指向同一个元素
                if (arr[ge] != arr[le]) {
                    swap(arr, ge, le); // 交换
                }
                ge++; // 处理下一个元素
                le--; // 处理下一个元素
            }
        }
        swap(arr, le, begin); // 将基准点元素放到合适位置，这里要用le，退出循环时，le在ge前面，前面的是小的
        return le;
    }

    /**
     * 交换数组中两个索引处的元素
     *
     * @param nums   数组
     * @param index1 索引1
     * @param index2 索引2
     */
    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }

    /**
     * 指定范围进行插入排序，用于数量较小的范围，不用优化为希尔排序，因为数量小性能差不多，插入更简单
     * @param nums 待排序数组
     * @param begin 起始索引（包含）
     * @param end 结束索引（包含）
     */
    private void insertionSort(int[] nums, int begin, int end) {
        for (int i = begin + 1; i <= end; i++){
            int inserted = nums[i]; // 待插入元素
            int index = i; // 记录插入位置
            while (index > begin && nums[index - 1] > inserted){
                nums[index] = nums[index - 1];
                index--; // 不能合并
            }
            if (index != i){
                nums[index] = inserted; // 插入
            }
        }
    }
}
